The present invention relates to the art of image processing It finds particular application in conjunction with determining and correcting image skew of a digital image, and will be described with particular reference thereto. It is to be appreciated, however, that the invention also finds application in conjunction with determining image skew in images acquired using a variety of image acquisition and output devices, such as scanners, and xerographic copiers and printers
Lines of text within images of scanned documents are typically brought into nearly upright orientation within a rotation of a multiple of 90 degrees The multiple describes the orientation of the image. For example, if the required rotation orientation is 0 or 180 degrees, the image is in portrait mode, while a required rotation orientation of 90 or 270 degrees indicates that the image is in landscape mode. After such rotation, the text lines, if they exist, typically have a small amount of skew, generally less than 5 degrees with respect to the raster lines
In many image processing applications, it is desirable to determine and correct skew of a document image. For example, many text recognition systems, such as optical character recognition (OCR) systems, fail if presented with text oriented with a skew of more than a few degrees, not to mention if the text is oriented sideways or upside-down. In addition, it is easier to identify text lines and text columns if the image skew is known or the image is deskewed.
A variety of methods for determining image skew have been proposed One approach involves using bounding boxes of connected components to estimate image skew. The coordinates of a token point, on the bottom center of the bounding box, are selected, and a function Stokens of skew angle is computed from these coordinates. Specifically, the function Stokens(θ) is the sum of squares of the number of such points computed along a set of lines with the angle θ to the raster direction A vertical shear is simulated on the set of points and the sums over the points with the same y-coordinate are determined Aside from a constant (independent of θ), the function Stokens is the variance of the number of tokens on a line, as a function of angle. This variance is a maximum in the direction where the tokens for each text line fall near the same line.
Another method for determining skew traverses straight lines of the image at a set of angles relative to the raster direction A function Sδ(θ) is computed that has a maximum value when the scan direction θ is along the text lines. Unlike the approach described above, which computes tokens from connected components, this method uses every pixel in the image. The function Sδ(θ) is similar to the function Stokens(θ) in the sense that an angle θ is chosen and pixel sums are found along lines in the image at this angle. However, instead of squaring the sum of tokens, the second method squares the difference between sums of ON pixels on adjacent lines, and the function Sδ(θ) is found by summing over all lines. The function Sδ(θ) is, aside from a constant, the variance in the difference between pixel sums on adjacent lines at the angle θ
The deskew methods described above, along with other deskew methods, use an iterative estimation approach based upon the method disclosed by Baird in U.S. Pat. No. 5,001,766. The Baird method requires a local copy of the image to be stored, thus obviating pipeline processing. Further, the iterative nature of Baird's method eliminates the possibility of parallel processing Therefore, the speed at which an image may be deskewed is necessarily limited Also, such iterative approaches may lead to local maximums instead of the correct global maximum and, therefore, report false angles in complex documents.
The present invention contemplates a new and improved method and apparatus for determining and correcting image skew, which overcomes the above-referenced problems and others.